package bTree.LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class 全排列2 {
    List<List<Integer>>res=new ArrayList<>();
    List<Integer>path=new ArrayList<>();
    HashSet<Integer> hashSet=new HashSet<>();//开在全局的，改为存放索引
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        backtracking(nums);
        return res;
    }

    private void backtracking(int[] nums) {
        if(path.size()==nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(i>0&&nums[i]==nums[i-1]&&!hashSet.contains(i-1)){//神来之笔
                continue;
            }
            if (!hashSet.contains(i)){
                path.add(nums[i]);
                hashSet.add(i);
                backtracking(nums);
                hashSet.remove(i);
                path.remove(path.size()-1);
            }
        }
    }
}